from typing import List


# 46. 全排列
# 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
def permute(nums: List[int]) -> List[List[int]]:
    re = list()

    loop_list = list()

    def back_track(count: int):

        if count == len(nums):
            re.append(loop_list[:])
            return

        for loop_index in range(len(nums)):
            # 不处理相等的元素
            loop_num = nums[loop_index]
            if loop_num in loop_list:
                continue

            count += 1
            loop_list.append(nums[loop_index])

            back_track(count)
            # 回溯
            loop_list.pop()
            count -= 1

    back_track(0)

    return re


nums_1 = [1, 2, 3]
result = permute(nums_1)
print(f"result:{result}")

nums_1 = [0, 1]
result = permute(nums_1)
print(f"result:{result}")

nums_1 = [1]
result = permute(nums_1)
print(f"result:{result}")
